package org.hhchat.leetcode.array;

import java.util.Scanner;



/**

 public int maxSubArray(int[] A) {
    int dp[] = new int[A.length]; int max = A[0]; dp[0] = A[0];
    for (int i = 1; i < A.length; i++) {
        dp[i] = Math.max(dp[i-1] + A[i] ,A[i]);
        max = Math.max(max, dp[i]);
    }
    return max;
 }

 */
public class code53_easy {
    public static class Solution {
        public int maxSubArray(int[] nums) {
            int dp[] = new int[nums.length];
            dp[0]=nums[0];
            for(int i=1;i<nums.length;i++) {
                dp[i] = dp[i - 1] + nums[i];
            }
            return result(dp);

        }


        private int result(int[] dp) {
            int max=-9999990;
            if(dp.length==1) return dp[0];
            for(int i=0;i<dp.length;i++) {
                for(int j=i+1;j<dp.length;j++) {
                    if (dp[j] - dp[i] > max) {
                        max=dp[j]-dp[i];
                    }
                }
                if (dp[i] > max) {
                    max=dp[i];
                }
            }
            return max;
        }
    }
    public static void main(String[] args){

        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            System.out.println(scanner.nextInt());
        }
    }
}
